package com.zdp.leetcode;



import java.util.*;
/*
* 题目描述：
* 给定仅有小写字母组成的字符串数组 A，返回列表中的每个字符串中都显示的全部字符（包括重复字符）组成的列表。例如，如果一个字符在每个字符串中出现 3 次，但不是 4 次，则需要在最终答案中包含该字符 3 次。
你可以按任意顺序返回答案。
示例 1：
输入：["bella","label","roller"]
输出：["e","l","l"]
示例 2：
输入：["cool","lock","cook"]
输出：["c","o"]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-common-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 查找常用字符 {
    public static void main(String[] args) {
        查找常用字符 demo = new 查找常用字符();
        demo.commonChars1(new String[]{
                "bella","label","roller"
        });
    }
    //利用两个map
    //map存储当前遍历过的所有字符串中重复出现的字符 和次数
    //map1 则是存储当前遍历的字符串中 重复字符 ===>map1根据 map来进行计算
    //如果当前字符 在map中有值，说明 之前的字符串中有该map，那么得到 该字符在map中的值，和在map1的值
    //将两者之间的较小值存入map1  当前字符串遍历结束，map指向map1
    public List<String> commonChars(String[] A) {
        Map<Character,Integer> map = new HashMap();
        for(int i=0;i<A[0].length();i++){
            Character c = A[0].charAt(i);
            map.put(c,map.getOrDefault(c, 0)+1);
        }
        for(int i=1;i<A.length;i++){
            Map<Character,Integer>map1 = new HashMap();
            System.out.println(A[i].length());
            for(int j=0;j<A[i].length();j++){
                Character c = A[i].charAt(j);
                if(map.containsKey(c)){
                    map1.put(c,Math.min(map.get(c),map1.getOrDefault(c,0)+1));
                }
            }
            map = map1;
        }
        List<String> r = new ArrayList();
        Set<Map.Entry<Character, Integer>> entries = map.entrySet();
        for(Map.Entry<Character,Integer> e:entries){
            for(int i=0;i<e.getValue();i++){
                r.add(e.getKey().toString());
            }
        }
        return r;
    }
    //因为字符全部都是小写字母，所以也可以直接用一个长度为26的数组来存储出现次数
    //思路跟上面其实是一样，只是占用的空间会少一点(好像没差多少，但是速度变快了）
    public List<String> commonChars1(String[] A) {
        int[] minCount = new int[26];
        Arrays.fill(minCount, Integer.MAX_VALUE);
        for(String s:A){
            int[] nowCount = new int[26];
            for(int i=0;i<s.length();i++){
                nowCount[s.charAt(i)-'a'] ++;
            }
            //改变一下mincount
            for(int i=0;i<26;i++){
                minCount[i] = Math.min(minCount[i],nowCount[i]);
            }
        }
        //生成字符串
        List<String> result = new ArrayList();
        for(int i=0;i<26;i++){
            for(int j=0;j<minCount[i];j++)
                result.add(String.valueOf((char)(i+'a')));
        }
        return result;
    }
}
